package com.lx.algorithm.code;

import java.util.Arrays;

/**
 * Description:
 * Copyright:   Copyright (c)2019
 * Company:     zefu
 *
 * @author: 张李鑫
 * @version: 1.0
 * Create at:   2021-12-29 23:48:20
 * <p>
 * Modification History:
 * Date         Author      Version     Description
 * ------------------------------------------------------------------
 * 2021-12-29     张李鑫                     1.0         1.0 Version
 */
public class Code01 {
    /**
     * 给定一个有序数组arr，从左到右依次表示X轴上从左往右点的位置
     * 给定一个正整数K，返回如果有一根长度为K的绳子，最多能盖住几个点
     * 绳子的边缘点碰到X轴上的点，也算盖住
     */

    /**
     * 单调栈实现
     *
     * @param arr
     * @param l
     * @return
     */
    public static int CordCoverMaxPoint(int[] arr, int l) {
        //设置左右两个指针
        int left = 0;
        int right = 0;
        //默认开始没有数字
        int res = 0;
        //从数组左边开始循环
        for (int i = 0; i < arr.length; i++) {
            //如果右边指针没有超过数组边界   arr[right] - arr[left] <= l说明能被绳子压住 右边指针一直走 走到压不住为止
            while (right < arr.length && arr[right] - arr[left] <= l) {
                right++;
            }
            // 统计当前单调栈里有多少数字 res记录 left++ 左边指针走一步.代表以上一个指针为头开始的所有数据已经统计完毕
            res = Math.max(res, right - (left++));
        }
        return res;
    }


    public static int[] generateArray(int len, int max) {
        int[] ans = new int[(int) (Math.random() * len) + 1];
        for (int i = 0; i < ans.length; i++) {
            ans[i] = (int) (Math.random() * max);
        }
        Arrays.sort(ans);
        return ans;
    }

    // for test
    public static int test(int[] arr, int L) {
        int max = 0;
        for (int i = 0; i < arr.length; i++) {
            int pre = i - 1;
            while (pre >= 0 && arr[i] - arr[pre] <= L) {
                pre--;
            }
            max = Math.max(max, i - pre);
        }
        return max;
    }

    public static int maxPoint2(int[] arr, int L) {
        int left = 0;
        int right = 0;
        int N = arr.length;
        int max = 0;
        while (left < N) {
            while (right < N && arr[right] - arr[left] <= L) {
                right++;
            }
            max = Math.max(max, right - (left++));
        }
        return max;
    }

    public static void main(String[] args) {
        int len = 100;
        int max = 1000;
        int testTime = 100000;
        System.out.println("测试开始");
        for (int i = 0; i < testTime; i++) {
            int L = (int) (Math.random() * max);
            int[] arr = generateArray(len, max);
            int ans1 = CordCoverMaxPoint(arr, L);
            int ans2 = maxPoint2(arr, L);
            int ans3 = test(arr, L);
            if (ans1 != ans2 || ans2 != ans3) {
                System.out.println("oops!");
                break;
            }
        }

    }

}